#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/12 18:37
# ===========================================
#       题目名称： 56. 合并区间
#       题目地址： https://leetcode.cn/problems/merge-intervals/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        merges = []
        # 排序
        intervals = sorted(intervals, key=lambda x: x[1])
        # 去重
        cur_index = 1
        while cur_index < len(intervals):
            if intervals[cur_index - 1] == intervals[cur_index]:
                del intervals[cur_index]
            else:
                cur_index += 1
        # 从后往前找
        # print(intervals)
        while intervals:
            target = intervals.pop()  # 目标元素
            cur_index = len(intervals) - 1  # 当前下标
            while cur_index > -1:
                source = intervals[cur_index]
                if target[0] > source[1]:
                    break
                target = [min(source[0], target[0]), max(source[1], target[1])]
                del intervals[cur_index]
                cur_index -= 1
            merges.append(target)
        return merges

    def merge4(self, intervals: List[List[int]]) -> List[List[int]]:
        merges = []
        # 排序
        intervals = sorted(intervals, key=lambda x: x[1])
        # 去重
        cur_index = 1
        while cur_index < len(intervals):
            if intervals[cur_index - 1] == intervals[cur_index]:
                del intervals[cur_index]
            else:
                cur_index += 1
        # 从后往前找

        while intervals:
            target = intervals.pop()  # 目标元素
            cur_index = len(intervals) - 1  # 当前下标
            while cur_index > -1:
                source = intervals[cur_index]
                new_arr = target + source
                new_arr.sort()
                if target == new_arr[:3] or target == new_arr[2:]:
                    if new_arr[1] == new_arr[2]:
                        target = [new_arr[0], new_arr[3]]
                        del intervals[cur_index]
                elif target[0] in new_arr[2:4] or target[1] in new_arr[2:4]:
                    target = [new_arr[0], new_arr[3]]
                    del intervals[cur_index]
                cur_index -= 1
            merges.append(target)
        return merges

    def merge3(self, intervals: List[List[int]]) -> List[List[int]]:
        """
            时间超时
        """
        merges = []
        cur_index = 0  # 当前下标
        intervals = sorted(intervals, key=lambda x: x[1])
        target = intervals.pop()
        while intervals:
            if cur_index < len(intervals):
                source = intervals[cur_index]
                # 判断 target 和 source 是否是包含关系
                cur_arr = target + source
                cur_arr.sort()
                # 1,2,3,4 1,2,2,4
                if target == cur_arr[:3] or target == cur_arr[2:]:
                    if cur_arr[1] == cur_arr[2]:
                        target = [cur_arr[0], cur_arr[3]]
                        del intervals[cur_index]
                        continue
                # [3,4][2,6]  [2,3,4,6]         [1,3][2,4]  [1,2,3,4]
                elif target[0] in cur_arr[2:4] or target[1] in cur_arr[2:4]:
                    target = [cur_arr[0], cur_arr[3]]
                    del intervals[cur_index]
                    continue
                # 移动下标
                if intervals:
                    if cur_index + 1 > len(intervals) - 1:
                        cur_index = 0
                        merges.append(target)
                        target = intervals.pop()
                    else:
                        cur_index += 1
                else:
                    merges.append(target)
            else:
                cur_index = 0  # 防止 当前index 比实际最大index要大
        merges.append(target)
        return merges

    def merge2(self, intervals: List[List[int]]) -> List[List[int]]:
        """
            实现有问题
        """
        # 0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
        # 0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0
        # 0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0
        # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1

        # 0,1,1,1,1,0
        # 0,0,0,0,1,1

        # 0,1,1,1,1,0,0
        # 0,0,0,0,0,1,1
        # 1. 寻找到最大的值
        max_val = 0
        for i in range(len(intervals)):
            cur_max_val = max(intervals[i])
            max_val = max(cur_max_val, max_val)
        # 2. 初始化一下
        dp = [[0] * (max_val + 1) for _ in range(len(intervals))]
        # 3. 填充
        for i in range(len(intervals)):
            x, y = intervals[i]
            dp[i][x: y + 1] = [1 for _ in range(x, y + 1)]
        # 4. 获取
        merges = []
        cur_index = 0
        x, y = -1, -1
        while cur_index <= max_val:
            cur_level_is_find = False
            for i in range(len(intervals)):
                if dp[i][cur_index] == 1:
                    cur_level_is_find = True
                    break
            if cur_level_is_find:
                if x == -1:
                    x = cur_index
                else:
                    y = cur_index
                    if cur_index == max_val:
                        merges.append([x, y])
            else:
                if not x == y == -1:
                    merges.append([x, y])
                    x = -1
                    y = -1
            cur_index += 1
        return merges


if __name__ == '__main__':
    s = Solution()
    # [[1,6],[8,10],[15,18]]
    print(s.merge(intervals=[[1, 3], [2, 6], [8, 10], [15, 18]]))
    # [[1,5]]
    print(s.merge(intervals=[[1, 4], [4, 5]]))
    # [[1,4],[5,6]]
    print(s.merge(intervals=[[1, 4], [5, 6]]))
    # [[0, 5]]
    print(s.merge(intervals=[[1, 4], [0, 5]]))
    # [[0,5]]
    print(s.merge(intervals=[[4, 5], [1, 4], [0, 1]]))
    # [[0,5]]
    print(s.merge(intervals=[[0, 1], [4, 5], [0, 2], [3, 4], [2, 4], [0, 0], [3, 5], [0, 1], [0, 0], [5, 5]]))
